๐Ÿ‘ฉโ€๐Ÿ’ป 14891. ํ†ฑ๋‹ˆ๋ฐ”ํ€ด

@Seongukbaek Posted March 06, 2022 ยท Updated March 06, 2022 ยท 9 min read

๋ฌธ์ œ

์ด 8๊ฐœ์˜ ํ†ฑ๋‹ˆ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ํ†ฑ๋‹ˆ๋ฐ”ํ€ด 4๊ฐœ๊ฐ€ ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์ผ๋ ฌ๋กœ ๋†“์—ฌ์ ธ ์žˆ๋‹ค. ๋˜, ํ†ฑ๋‹ˆ๋Š” N๊ทน ๋˜๋Š” S๊ทน ์ค‘ ํ•˜๋‚˜๋ฅผ ๋‚˜ํƒ€๋‚ด๊ณ  ์žˆ๋‹ค. ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์—๋Š” ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ๋Š”๋ฐ, ๊ฐ€์žฅ ์™ผ์ชฝ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๊ฐ€ 1๋ฒˆ, ๊ทธ ์˜ค๋ฅธ์ชฝ์€ 2๋ฒˆ, ๊ทธ ์˜ค๋ฅธ์ชฝ์€ 3๋ฒˆ, ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋Š” 4๋ฒˆ์ด๋‹ค.

์ด๋•Œ, ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋ฅผ ์ด K๋ฒˆ ํšŒ์ „์‹œํ‚ค๋ ค๊ณ  ํ•œ๋‹ค. ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ํšŒ์ „์€ ํ•œ ์นธ์„ ๊ธฐ์ค€์œผ๋กœ ํ•œ๋‹ค. ํšŒ์ „์€ ์‹œ๊ณ„ ๋ฐฉํ–ฅ๊ณผ ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์ด ์žˆ๋‹ค.

ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋ฅผ ํšŒ์ „์‹œํ‚ค๋ ค๋ฉด, ํšŒ์ „์‹œํ‚ฌ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์™€ ํšŒ์ „์‹œํ‚ฌ ๋ฐฉํ–ฅ์„ ๊ฒฐ์ •ํ•ด์•ผ ํ•œ๋‹ค. ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๊ฐ€ ํšŒ์ „ํ•  ๋•Œ, ์„œ๋กœ ๋งž๋‹ฟ์€ ๊ทน์— ๋”ฐ๋ผ์„œ ์˜†์— ์žˆ๋Š” ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋ฅผ ํšŒ์ „์‹œํ‚ฌ ์ˆ˜๋„ ์žˆ๊ณ , ํšŒ์ „์‹œํ‚ค์ง€ ์•Š์„ ์ˆ˜๋„ ์žˆ๋‹ค. ํ†ฑ๋‹ˆ๋ฐ”ํ€ด A๋ฅผ ํšŒ์ „ํ•  ๋•Œ, ๊ทธ ์˜†์— ์žˆ๋Š” ํ†ฑ๋‹ˆ๋ฐ”ํ€ด B์™€ ์„œ๋กœ ๋งž๋‹ฟ์€ ํ†ฑ๋‹ˆ์˜ ๊ทน์ด ๋‹ค๋ฅด๋‹ค๋ฉด, B๋Š” A๊ฐ€ ํšŒ์ „ํ•œ ๋ฐฉํ–ฅ๊ณผ ๋ฐ˜๋Œ€๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•˜๊ฒŒ ๋œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์•„๋ž˜์™€ ๊ฐ™์€ ๊ฒฝ์šฐ๋ฅผ ์‚ดํŽด๋ณด์ž.

๋‘ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ๋งž๋‹ฟ์€ ๋ถ€๋ถ„์€ ์ดˆ๋ก์ƒ‰ ์ ์„ ์œผ๋กœ ๋ฌถ์—ฌ์žˆ๋Š” ๋ถ€๋ถ„์ด๋‹ค. ์—ฌ๊ธฐ์„œ, 3๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋ฅผ ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ–ˆ๋‹ค๋ฉด, 4๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋Š” ์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•˜๊ฒŒ ๋œ๋‹ค. 2๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋Š” ๋งž๋‹ฟ์€ ๋ถ€๋ถ„์ด S๊ทน์œผ๋กœ ์„œ๋กœ ๊ฐ™๊ธฐ ๋•Œ๋ฌธ์—, ํšŒ์ „ํ•˜์ง€ ์•Š๊ฒŒ ๋˜๊ณ , 1๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋Š” 2๋ฒˆ์ด ํšŒ์ „ํ•˜์ง€ ์•Š์•˜๊ธฐ ๋•Œ๋ฌธ์—, ํšŒ์ „ํ•˜์ง€ ์•Š๊ฒŒ ๋œ๋‹ค. ๋”ฐ๋ผ์„œ, ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์€ ๋ชจ์–‘์„ ๋งŒ๋“ค๊ฒŒ ๋œ๋‹ค.

1๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋ฅผ ์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „์‹œํ‚ค๋ฉด, 2๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๊ฐ€ ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•˜๊ฒŒ ๋˜๊ณ , 2๋ฒˆ์ด ํšŒ์ „ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, 3๋ฒˆ๋„ ๋™์‹œ์— ์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•˜๊ฒŒ ๋œ๋‹ค. 4๋ฒˆ์€ 3๋ฒˆ์ด ํšŒ์ „ํ•˜์ง€๋งŒ, ๋งž๋‹ฟ์€ ๊ทน์ด ๊ฐ™๊ธฐ ๋•Œ๋ฌธ์— ํšŒ์ „ํ•˜์ง€ ์•Š๋Š”๋‹ค. ๋”ฐ๋ผ์„œ, ์•„๋ž˜์™€ ๊ฐ™์€ ์ƒํƒœ๊ฐ€ ๋œ๋‹ค.

ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ดˆ๊ธฐ ์ƒํƒœ์™€ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋ฅผ ํšŒ์ „์‹œํ‚จ ๋ฐฉ๋ฒ•์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ตœ์ข… ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ƒํƒœ๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…, ์ถœ๋ ฅ

์ž…๋ ฅ

  • ์ฒซ์งธ ์ค„์— 1๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ƒํƒœ, ๋‘˜์งธ ์ค„์— 2๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ƒํƒœ, ์…‹์งธ ์ค„์— 3๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ƒํƒœ, ๋„ท์งธ ์ค„์— 4๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ƒํƒœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ƒํƒœ๋Š” 8๊ฐœ์˜ ์ •์ˆ˜๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , 12์‹œ๋ฐฉํ–ฅ๋ถ€ํ„ฐ ์‹œ๊ณ„๋ฐฉํ–ฅ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. N๊ทน์€ 0, S๊ทน์€ 1๋กœ ๋‚˜ํƒ€๋‚˜์žˆ๋‹ค.
  • ๋‹ค์„ฏ์งธ ์ค„์—๋Š” ํšŒ์ „ ํšŸ์ˆ˜ K(1 โ‰ค K โ‰ค 100)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ K๊ฐœ ์ค„์—๋Š” ํšŒ์ „์‹œํ‚จ ๋ฐฉ๋ฒ•์ด ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ๋ฐฉ๋ฒ•์€ ๋‘ ๊ฐœ์˜ ์ •์ˆ˜๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , ์ฒซ ๋ฒˆ์งธ ์ •์ˆ˜๋Š” ํšŒ์ „์‹œํ‚จ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ๋ฒˆํ˜ธ, ๋‘ ๋ฒˆ์งธ ์ •์ˆ˜๋Š” ๋ฐฉํ–ฅ์ด๋‹ค. ๋ฐฉํ–ฅ์ด 1์ธ ๊ฒฝ์šฐ๋Š” ์‹œ๊ณ„ ๋ฐฉํ–ฅ์ด๊ณ , -1์ธ ๊ฒฝ์šฐ๋Š” ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์ด๋‹ค.

์ถœ๋ ฅ

  • ์ด K๋ฒˆ ํšŒ์ „์‹œํ‚จ ์ดํ›„์— ๋„ค ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ ์ˆ˜์˜ ํ•ฉ์„ ์ถœ๋ ฅํ•œ๋‹ค. ์ ์ˆ˜๋ž€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ณ„์‚ฐํ•œ๋‹ค.

    • 1๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ 12์‹œ๋ฐฉํ–ฅ์ด N๊ทน์ด๋ฉด 0์ , S๊ทน์ด๋ฉด 1์ 
    • 2๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ 12์‹œ๋ฐฉํ–ฅ์ด N๊ทน์ด๋ฉด 0์ , S๊ทน์ด๋ฉด 2์ 
    • 3๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ 12์‹œ๋ฐฉํ–ฅ์ด N๊ทน์ด๋ฉด 0์ , S๊ทน์ด๋ฉด 4์ 
    • 4๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ 12์‹œ๋ฐฉํ–ฅ์ด N๊ทน์ด๋ฉด 0์ , S๊ทน์ด๋ฉด 8์ 

๐Ÿ“ Logic

class Gear { int[] tooth; boolean spinStatus; int spinDir; public Gear() { tooth = new int[8]; spinStatus = false; spinDir = 0; } public void clockWise() { int tmp = tooth[7]; System.arraycopy(tooth, 0, tooth, 1, 7); tooth[0] = tmp; } public void counterClockWise() { int tmp = tooth[0]; System.arraycopy(tooth, 1, tooth, 0, 7); tooth[7] = tmp; } }
  • ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ •๋ณด๋ฅผ ์ €์žฅํ•˜๋Š” ํด๋ž˜์Šค์ด๋‹ค.
  • clockWise() ๋Š” ํ†ฑ๋‹ˆ๋ฅผ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ๋Œ๋ ธ์„ ๋•Œ ์ƒํƒœ ์—…๋ฐ์ดํŠธ๋ฅผ ์ˆ˜ํ–‰ํ•˜๊ณ , counterClockWise() ๋Š” ๋ฐ˜์‹œ๊ณ„๋ฐฉํ–ฅ์— ๋Œ€ํ•œ ์—…๋ฐ์ดํŠธ๋ฅผ ์ˆ˜ํ–‰ํ•œ๋‹ค.
for (int i = 0; i < N; i++) { spins[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); int centerG = spins[i][0] - 1; gears[centerG].spinStatus = true; gears[centerG].spinDir = spins[i][1]; for (int j = centerG - 1; j >= 0; j--) { if (gears[j + 1].spinStatus) { if (gears[j].tooth[2] != gears[j + 1].tooth[6]) { gears[j].spinStatus = true; gears[j].spinDir = gears[j + 1].spinDir * -1; } } } for (int j = centerG + 1; j < 4; j++) { if (gears[j - 1].spinStatus) { if (gears[j].tooth[6] != gears[j - 1].tooth[2]) { gears[j].spinStatus = true; gears[j].spinDir = gears[j - 1].spinDir * -1; } } } for (int j = 0; j < 4; j++) { if (gears[j].spinDir == -1) gears[j].counterClockWise(); else if (gears[j].spinDir == 1) gears[j].clockWise(); gears[j].spinDir = 0; gears[j].spinStatus = false; } }
  • ์ค‘์‹ฌ ๊ตฌํ˜„๋ถ€๋Š” ํฌ๊ฒŒ 3๊ฐœ๋กœ ๋‚˜๋ˆŒ ์ˆ˜ ์žˆ๋‹ค.

    • ํšŒ์ „ํ•˜๋Š” ํ†ฑ๋‹ˆ์˜ ์™ผ์ชฝ ํ†ฑ๋‹ˆ์— ๋Œ€ํ•ด ํšŒ์ „์—ฌ๋ถ€๋ฅผ ํŒ๋‹จํ•˜๊ณ  ์ˆ˜ํ–‰ํ•˜๋Š” for๋ฌธ
    • ํšŒ์ „ํ•˜๋Š” ํ†ฑ๋‹ˆ์˜ ์˜ค๋ฅธ์ชฝ ํ†ฑ๋‹ˆ์— ๋Œ€ํ•ด ํšŒ์ „์—ฌ๋ถ€๋ฅผ ํŒ๋‹จํ•˜๊ณ  ์ˆ˜ํ–‰ํ•˜๋Š” for๋ฌธ
    • ์ฃผ์–ด์ง„ 1ํšŒ์ „์ด ๋๋‚œ ํ›„ ํ†ฑ๋‹ˆ์˜ ์ •๋ณด๋ฅผ ์—…๋ฐ์ดํŠธํ•˜๋Š” for๋ฌธ

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Gear { int[] tooth; boolean spinStatus; int spinDir; public Gear() { tooth = new int[8]; spinStatus = false; spinDir = 0; } public void clockWise() { int tmp = tooth[7]; System.arraycopy(tooth, 0, tooth, 1, 7); tooth[0] = tmp; } public void counterClockWise() { int tmp = tooth[0]; System.arraycopy(tooth, 1, tooth, 0, 7); tooth[7] = tmp; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Gear[] gears = new Gear[4]; for (int i = 0; i < 4; i++) { gears[i] = new Gear(); gears[i].tooth = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray(); } int N = Integer.parseInt(br.readLine()); int[][] spins = new int[N][2]; for (int i = 0; i < N; i++) { spins[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); int centerG = spins[i][0] - 1; gears[centerG].spinStatus = true; gears[centerG].spinDir = spins[i][1]; for (int j = centerG - 1; j >= 0; j--) { if (gears[j + 1].spinStatus) { if (gears[j].tooth[2] != gears[j + 1].tooth[6]) { gears[j].spinStatus = true; gears[j].spinDir = gears[j + 1].spinDir * -1; } } } for (int j = centerG + 1; j < 4; j++) { if (gears[j - 1].spinStatus) { if (gears[j].tooth[6] != gears[j - 1].tooth[2]) { gears[j].spinStatus = true; gears[j].spinDir = gears[j - 1].spinDir * -1; } } } for (int j = 0; j < 4; j++) { if (gears[j].spinDir == -1) gears[j].counterClockWise(); else if (gears[j].spinDir == 1) gears[j].clockWise(); gears[j].spinDir = 0; gears[j].spinStatus = false; } } N = 0; for (int i = 0; i < 4; i++) N += gears[i].tooth[0] * Math.pow(2,i); System.out.println(N); br.close(); } }

โœ๏ธ Review

  • ์ •๋ง ์˜ค๋žœ๋งŒ์— 1ํŠธ๋งŒ์— ์„ฑ๊ณตํ–ˆ๋‹ค. ๋‚œ์ด๋„ ๋†’์€ ๋ฌธ์ œ๋Š” ์•„๋‹ˆ์—ˆ์ง€๋งŒ ...
  • ๋ฌธ์ œ ํ’€์ด๋ฅผ ๊ตฌ์ƒํ•˜๋ฉด์„œ, ์–ด๋–ค ๋ฉ”์†Œ๋“œ๋ฅผ ๊ตฌํ˜„ํ•ด์•ผํ•˜๋ฉฐ, ์–ด๋–ค ๋ฉ”์†Œ๋“œ๋ฅผ ๊ฐ์ฒด์— ๋‘ฌ์•ผ ํ•˜๋Š”์ง€์— ๋Œ€ํ•ด ์ข€ ๋” ๊ณต๋ถ€ํ•ด๋ด์•ผ๊ฒ ๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

Baekjoon : https://www.acmicpc.net/problem/14891

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€